package jjn.round1;

import java.util.List;

/**
 * @author Jjn
 * @since 2023/4/30 22:04
 */
public class LeetCode120_Triangle {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty()) {
            return 0;
        }
        int[][] path = new int[triangle.size()][triangle.size()];
        path[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            path[i][0] = path[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                path[i][j] = Math.min(path[i - 1][j - 1], path[i - 1][j]) + triangle.get(i).get(j);
            }
            path[i][i] = path[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = path[triangle.size() - 1][0];
        
        List<Integer> lastLine = triangle.get(triangle.size() - 1);
        for (int i = 0; i < lastLine.size(); i++) {
            if (minTotal > path[triangle.size() - 1][i]) {
                minTotal = path[triangle.size() - 1][i];
            }
        }
        return minTotal;
    }
}
